import java.util.Arrays;
import java.util.Queue;

public class Solution {


    //七大排序算法：默认按照从小到大的原则排序
    private void swap(int a, int b, int[] array) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    //1.直接插入排序
    public int[] Insert_sort(int[] array) {
        for (int j = 1; j < array.length; j++) {  //j = 1,2,3,4,5

            int i = j - 1;
            int key = array[j];  //key为将要插入的元素

            //找到合适的位置插入
            while (i >= 0 && array[i] > key) {
                array[i + 1] = array[i];
                i--;
            }
            array[i + 1] = key;
        }
        return array;
    }

    public int[] Insert_sort(int[] array, int left, int right) {
        for (int j = left + 1; j <= right; j++) {  //j = 1,2,3,4,5

            int i = j - 1;
            int key = array[j];  //key为将要插入的元素

            //找到合适的位置插入
            while (i >= 0 && array[i] > key) {
                array[i + 1] = array[i];
                i--;
            }
            array[i + 1] = key;
        }
        return array;
    }


    //2.希尔排序 ：使用分组（预排序）   是对直接插入排序的优化
    public int[] shell_sort(int[] array) {
        int gap = array.length / 2;   //5,2,1
        while (gap > 1) {//不管怎么分组，最后都会到一组，进行最有序的插入排序
            for (int i = 0; i < gap - 1; i++) {
                //每组的插入排序
                if (array[i] > array[i + gap]) {
                    swap(i, i + gap, array);  //   0,4 / 1,5 / 2,6 / 3,7 / 4,8 / 5,9/
                }
            }
            gap /= 2;
        }

        //此时gap应该等于1，执行插入排序
        Insert_sort(array);
        return array;
    }

    //3.选择排序：每次从待排序的数组选择最小（最大）的元素，并放置在数组的前列
    public int[] select_sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { //最后一个元素不换
            int key = i + 1;
            for (int j = i + 1; j < array.length; j++) {
                //从i的元素后面找到最小的元素并与i交换
                if (array[key] > array[j]) {
                    key = j;
                }
                if (j == array.length - 1 && array[key] < array[i]) {   //并不是 j 查出来的最小值都要与array[i] 交换，array 是一个有序的数组，所以 array[j] 要和 array[i] 比一比
                    swap(key, i, array);
                }
            }
        }
        return array;
    }

    //4.快速排序 ： 二叉树加递归
    public void Quick_sort(int[] array) {
        quick(array, 0, array.length - 1);  //基准为数组的第一个数据
    }


    private static int middle_num(int[] array, int left, int right) {
        int middle = (left + right) / 2;

        if (array[left] < array[right]) {
            if (array[middle] < array[left]) {
                return left;
            } else if (array[middle] > array[right]) {
                return right;
            } else return middle;
        } else {
            if (array[middle] < array[right]) {
                return right;
            } else if (array[middle] > array[left]) {
                return left;
            } else return middle;
        }
    }


    public void quick(int[] array, int start, int end) {
        if (start >= end)
            return;

        if (end - start + 1 <= 15) {
            Insert_sort(array, start, end);
        }

        /*
        换基准值进行优化
         */
        int index = middle_num(array, start, end);
        swap(index, start, array);

        int Benchmark_value = function(array, start, end);
        quick(array, start, Benchmark_value - 1);
        quick(array, Benchmark_value + 1, end);
    }


    //找到数组中的基准值
    public int function(int[] array, int left, int right) {
        int tmp = array[left];

        int i = left;
        while (left < right) {  //
//            //前半段找到比基准值大的
//            while (left < right && array[left] <= tmp)
//                left++;

            /*
               先走左边left停到基准值较大的数据，就会导致左边会存在较大的数据
             */


            //后半段找到比基准值小的
            while (left < right && array[right] >= tmp)
                right--;

            while (left < right && array[left] <= tmp)
                left++;

            //找到之后进行一次交换
            swap(left, right, array);
        }
        //此时left和right相遇，交换left位置和0上的值
        swap(left, i, array);
        return left;
    }

    public void Merge_sort(int[] array) {
        MergesortFun(array, 0, array.length - 1);
    }


    public void MergesortFun(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        MergesortFun(array, start, mid);
        MergesortFun(array, mid + 1, end);
        Merge(array, start, end, mid);
    }

    private void Merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid + 1;

        //定义一个新的数组
        int[] tmpArr = new int[right - left + 1];
        int k = 0;  //tmpArr数组的下标
        while (s1 <= mid && s2 <= right) {
            if (array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            } else {
                tmpArr[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= right) {
            tmpArr[k++] = array[s2++];
        }

        System.arraycopy(tmpArr, 0, array, left, tmpArr.length);
    }
}